using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Linq.Dynamic;
using YTS.Tools;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0102. 二叉树的层序遍历")]
    public class No0102_LevelOrder : AbsBaseTestItem
    {
        public override void OnTest()
        {
            Assert.TestExe(LevelOrder,
                new TreeNode(3)
                {
                    left = new TreeNode(9),
                    right = new TreeNode(20)
                    {
                        left = new TreeNode(15),
                        right = new TreeNode(7),
                    },
                },
                new int[][]
                {
                    new int[] { 3 },
                    new int[] { 9, 20 },
                    new int[] { 15, 7 },
                });
        }

        public class TreeNode
        {
            public int val;
            public TreeNode left;
            public TreeNode right;
            public TreeNode(int x) { val = x; }
        }
        public IList<IList<int>> LevelOrder(TreeNode root)
        {
            List<IList<int>> ret = new List<IList<int>>();
            if (root == null)
                return ret;

            List<TreeNode> q = new List<TreeNode>();
            q.Add(root);
            while (q.Count != 0)
            {
                int currentLevelSize = q.Count;
                ret.Add(new List<int>());
                for (int i = 1; i <= currentLevelSize; ++i)
                {
                    TreeNode node = q.First();
                    q.Remove(node);
                    ret[ret.Count - 1].Add(node.val);
                    if (node.left != null) q.Add(node.left);
                    if (node.right != null) q.Add(node.right);
                }
            }

            return ret;
        }
    }
}
